package leetcode.offer;

@SuppressWarnings("all")
public class _169_数组中出现次数超过一半的数字 {

    public int majorityElement(int[] nums) {
        // 我们维护一个候选众数 candidate 和它出现的次数 count
        // 初始时 candidate 可以为任意值，count 为 0
        int count = 0;
        Integer candidate = null;

        // 遍历数组 nums 中的所有元素
        for (int num : nums) {
            // 对于每个元素 num，在判断 num 之前，如果 count 的值为 0，我们先将 num 的值赋予 candidate
            // 这个判断使 count 的值在遍历的过程中一直保持非负
            if (count == 0) {
                candidate = num;
            }
            // 如果 num 与 candidate 相等，那么计数器 count 的值增加 1
            // 如果 num 与 candidate 不等，那么计数器 count 的值减少 1
            count += (num == candidate) ? 1 : -1;
        }
        // 在遍历完成后，candidate 即为整个数组的众数
        assert candidate != null;
        return candidate;
    }
    // 1,1,1,2,2
    // 2,2,1,1,1
}
